package Intermediate_algorithm.TreeAndGraph;

import java.util.HashMap;
import java.util.Map;

/*
从前序与中序遍历序列构造二叉树
给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/data-structure-binary-tree/xoei3r/
 */
public class _03从前序与中序遍历序列构造二叉树 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //递归
    /*
    只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
    因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
    问题一：怎样快速的得到前序遍历中根节点在中序遍历中对应的index序号
    答：维护一个以中序遍历的值为键、index序号为值的HashMap
    问题二：递归中怎么知道当前前序遍历的index序号
    答：维护一个preIndex来记录前序遍历的序号
    问题三：递归的出口应当是什么？
    答：当左右括号不成立时，代表当前结点没有子树，应当退出递归，return null;
    */
    //ps: 在树的问题中 public TreeNode dfs(){} 的结构可以在递归过程中通过root.left等将各个新结点连接起来，而在最终返回root根结点
    class Solution {
        int[] preorder;
        int[] inorder;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int preIndex = 0;

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            this.inorder = inorder;
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return dfs(0, preorder.length - 1);
        }

        public TreeNode dfs(int left, int right) {
            if (left > right) {
                return null;
            }
            int val = preorder[preIndex];
            TreeNode root = new TreeNode(val);
            preIndex++;
            int index = map.get(val);
            root.left = dfs(left, index - 1);
            root.right = dfs(index + 1, right);
            return root;
        }

    }


}
